package com.jhy.review.day01;

import java.util.ArrayList;
import java.util.List;

/**
 * 判断一个树是否是搜索二叉树
 * 搜索二叉树 左子树的节点都小于右子树
 * 就相当于是中序排序 从小到大的排列
 * BST
 * <p>
 * 2022年7月20日15:46:39
 */
public class SearchBinaryTrees {
    private static int preValue = Integer.MIN_VALUE;

    public static Boolean checkBST(Node head) {
        // 定义一个提前的值
        if (head == null) {
            return true;
        }
        // 先判断左节点,如果左节点为false，那么我们直接返回
        Boolean lBoolean = checkBST(head.left);
        if (!lBoolean) {
            return false;
        }
        // 这是之前来打印中序当中的值的 我们现在来作为判断
        // 一旦当前节点的值小于这个值
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return checkBST(head.right);
    }

    // 方法2不用在递归里面动态判断值的效果
    public static Boolean checkBST2(Node node) {
        Boolean flag = true;
        List<Node> list = new ArrayList<>();
        process2(node, list);
        for (int i = 0; i < list.size(); i++) {
            int value = list.get(i).value;
            if (value <= preValue) {
                flag = false;
            }
            preValue = value;
        }
        return flag;
    }

    public static void process2(Node node, List<Node> InOrderArrayList) {
        if (node == null) {
            return;
        }
        process2(node.left, InOrderArrayList);
        // 这个集合当中就已经中序排序的node了
        InOrderArrayList.add(node);
        process2(node.right, InOrderArrayList);
    }

    // 方法 3
    // 先定义一个数据返回类型
    public static class ReturnData {
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    /**
     * 2022年7月21日15:11:19
     * 树形DP方法解决
     * 左树和右树都是搜索二叉树
     * 左树的最大值小于我
     * 右树的最小值大于我
     * 左树是搜索二叉树 最大值
     * 右树是搜索二叉树 最小值
     * 递归要求要一样
     * 所以我们一律返回三个信息
     *
     *
     *
     * @param x
     * @return
     */
    public static ReturnData checkBST3(Node x) {
        if (x == null) {
            return null;
        }
        // 相当于这两个东西就是一种黑盒，我们利用里面的属性办事就好了。
        ReturnData leftData = checkBST3(x.left);
        ReturnData rightData = checkBST3(x.right);

        // 现在的问题就是我们的最后一个节点怎么能将三个属性给连接起来
        // 先声明三个属性
        int min = x.value;
        int max = x.value;

        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }

        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }
        // 先假设这个属性是true
        boolean isBST = true;
        // 如果有以下的情况 就是违规了。那么就为FALSE了
        // 如果左边有数据且（左边不是搜索树 或者 左边的最大值 已经大于了 当前节点）isBST就FALSE了
        if(
                leftData != null && (!leftData.isBST || leftData.max >= x.value)
        )
        {
            isBST = false;
        }
        // 如果右边有数据且（右边不是搜索树或者当前节点的值大于右边的节点的最小值）
        if(
                rightData != null && (!rightData.isBST || x.value >= rightData.min)
        ){
            isBST = true;
        }
        // 说明都达标了
        return new ReturnData(isBST, min, max);
    }
}
